package map_set.leetcode.medium;

import java.util.*;

/**
 * @author bruin_du
 * @description 插入、删除和随机访问都是 O(1) 的容器
 * @date 2022/8/11 16:59
 **/
public class OfferII030_RandomizedSet {
    List<Integer> list;
    Map<Integer, Integer> map;
    Random random;
    /** Initialize your data structure here. */
    public OfferII030_RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();
        random = new Random();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (!map.containsKey(val)) {
            list.add(val);
            map.put(val, list.size() - 1);
            return true;
        }
        return false;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (map.containsKey(val)) {
            int index = map.get(val);
            int num = list.get(list.size() - 1);
            list.set(index, num);
            map.put(num, index);
            list.remove(list.size() - 1);
            map.remove(val);
            return true;
        }
        return false;
    }

    /** Get a random element from the set. */
    public int getRandom() {
        int randomIndex = random.nextInt(list.size());
        return list.get(randomIndex);
    }
}
